/**
 * @author ChaP
 * @date 2019/05/12
 * @describe:
 */
package CodingTest.AC20190512;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
 */
public class levelOrder {
    class Node{
        public int val;
        public List<Node> children;
        public Node(){}
        public Node(int _val,List<Node> _children){
            val = _val;
            children = _children;
        }
    }
    public List<List<Integer>> levelOrder(Node root){
        if(root == null) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        Node temp = null;
          while(!queue.isEmpty()){
              List<Integer> tmpList = new ArrayList<Integer>();
              int size = queue.size();
              for(int i = 0;i<size;i++){
                  temp = queue.poll();
                  for(Node n :temp.children){
                      queue.offer(n);
                  }
                  tmpList.add(temp.val);
              }
              res.add(tmpList);
          }
          return res;

    }
}
